package 字符子串查找;

import java.util.Arrays;

/**
 * 字符子串查找
 * 给定两个字符串A、B，判断B在A中是否存在，存在返回A中的下标，不存在返回-1
 */
public class Solution {
    public static void main(String[] args) {

        System.out.println(searchUseHash("BCADBCABCADBCD", "BCADBCD"));
        System.out.println(searchUseHash("BCADBCABCADBC1D", "BCADBCD"));

        System.out.println(searchUseKMP("BCADBCABCADBCD".toCharArray(), "BCADBCD".toCharArray()));
        System.out.println(searchUseKMP("BCADBCABCADBC1D".toCharArray(), "BCADBCD".toCharArray()));
        System.out.println(searchUseKMP("ABCABCABCABCD".toCharArray(), "ABCABCD".toCharArray()));
    }

    /**
     * KMP
     * 模式串：查找的子串
     * 前缀：A = B + S
     * 后缀：A = S + B
     * PMT：前缀集合和后缀集合的交集中，最长元素的长度
     * 部分匹配表：PMT值集合，字符串的所有前缀的PMT值
     * prefix数组：每一个下标位置对应一个PMT值，组成的数组
     * next数组：prefix向右移一个下标位置，组成next数组
     * <p>
     * A   B  C  A  B  C  D    模式串
     * 0   1  2  3  4  5  6    子串下标
     * 0   0  0  1  2  3  0    PMT值(prefix数组)
     * -1  0  0  0  1  2  3    next数组（如何构建）
     */
    public static int searchUseKMP(char[] s, char[] pattern) {

        int[] nextArr = buildNextArr(pattern);
        System.out.println("nextArr = " + Arrays.toString(nextArr));

        int i = 0;
        int j = 0;
        while (i < s.length
                // 模式串匹配到了最后，说明找到了
                && j < pattern.length
        ) {
            if (j == -1 || s[i] == pattern[j]) {
                i++;
                j++;
            } else {
                j = nextArr[j];
            }
        }

        if (j == pattern.length) {
            // 模式串匹配到了最后，说明找到了
            return i - j;
        } else {
            return -1;
        }
    }

    private static int[] buildNextArr(char[] pattern) {
        /*
        A   B   C   A   B   C   D
                    A   B   C   A   B   C   D
         */
        int j = 1;
        int i = 0;
        int[] nextArr = new int[pattern.length];
        nextArr[0] = -1;

        while (j < pattern.length) {
            if (i == -1) {
                i++;
                j++;
            } else if (pattern[i] == pattern[j]) {
                i++;
                j++;
                nextArr[j] = i;
            } else {
                i = nextArr[i];
            }
        }
        return nextArr;
    }

    public static int searchUseHash(String s, String sub) {
        int hash = 0;
        for (char c : sub.toCharArray()) {
            hash += c;
        }

        int hh = 0;
        int p = 0;
        for (int i = 0; i < sub.length(); i++) {
            hh += s.charAt(i);
        }
        while (true) {
            if (hash == hh && eq(s, sub, p)) {
                return p;
            }

            if (p + sub.length() == s.length()) {
                break;
            }

            hh -= s.charAt(p);
            hh += s.charAt(p + sub.length());

            p++;
        }
        return -1;
    }

    private static boolean eq(String s, String sub, int p) {
        for (int i = 0; i < sub.length(); i++) {
            if (s.charAt(p + i) != sub.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}
